P4900 食堂

题目需要求的是这个式子：

$\sum_{i=A}^B\sum_{j=1}^i \{\frac{i}{j}\}$

由小学奥数知识可知：$\{x\}=x-[x]$

所以上式等价于：

$\sum_{i=A}^B\sum_{j=1}^i(\frac{i}{j}-[\frac{i}{j}])$

$\sum_{i=A}^B\sum_{j=1}^i\frac{i}{j}-\sum_{i=A}^B\sum_{j=1}^i[\frac{i}{j}]$

先看前部分，

$\sum_{i=A}^B\sum_{j=1}^i\frac{i}{j}$

$\sum_{i=A}^Bi\sum_{j=1}^i inv[j]$

递推求出 $inv$ 数组，做前缀和后与 $i$ 相乘，记为 $fir$

再将 $fir$ 数组求前缀和后得到第一部分答案。

再看后部分，

$\sum_{i=A}^B\sum_{j=1}^i[\frac{i}{j}]$

$\sum_{i=A}^B\sum_{j=1}^id(j)$

线性筛出约数个数后求两次前缀和即可。

时间复杂度 $\Theta(n+t)$。

#include <cstdio>
#define Mod 998244353

const int MAXN = 1000000;
int t , l , r , k , d[ MAXN + 5 ] , num[ MAXN + 5 ] , prime[ MAXN + 5 ];
int inv[ MAXN + 5 ] , pre_inv[ MAXN + 5 ];
int fir[ MAXN + 5 ] , sec[ MAXN + 5 ];
bool vis[ MAXN + 5 ];

void sieve( ) {
    d[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
        if( !vis[ i ] ) {
            prime[ ++ k ] = i;
            d[ i ] = 2 , num[ i ] = 1;
        }
        for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
            vis[ i * prime[ j ] ] = 1;
            if( i % prime[ j ] == 0 ) {
                d[ i * prime[ j ] ] = d[ i ] / ( num[ i ] + 1 ) * ( num[ i ] + 2 );
                num[ i * prime[ j ] ] = num[ i ] + 1;
                break;
            }
            d[ i * prime[ j ] ] = d[ i ] * d[ prime[ j ] ];
            num[ i * prime[ j ] ] = 1;
        }
    }
}
void Init( ) {
    inv[ 0 ] = inv[ 1 ] = 1;
    for( int i = 2 ; i <= MAXN ; i ++ )
        inv[ i ] = 1ll * ( Mod - Mod / i ) * inv[ Mod % i ] % Mod;
    for( int i = 1 ; i <= MAXN ; i ++ )
       pre_inv[ i ] = ( pre_inv[ i - 1 ] + inv[ i ] ) % Mod;

    for( int i = 1 ; i <= MAXN ; i ++ )
        fir[ i ] = 1ll * i * pre_inv[ i ] % Mod;
    for( int i = 1 ; i <= MAXN ; i ++ )
        fir[ i ] = ( fir[ i - 1 ] + fir[ i ] ) % Mod;
    
    sieve( );
    for( int i = 1 ; i <= MAXN ; i ++ )
        sec[ i ] = ( sec[ i - 1 ] + d[ i ] ) % Mod;
    for( int i = 1 ; i <= MAXN ; i ++ )
        sec[ i ] = ( sec[ i - 1 ] + sec[ i ] ) % Mod;
}

int main( ) {
    Init( );
    scanf("%d",&t);
    while( t -- ) {
        scanf("%d %d",&l,&r);
        printf("%d\n", ( ( fir[ r ] - fir[ l - 1 ] + Mod ) % Mod - ( sec[ r ] - sec[ l - 1 ] + Mod ) % Mod + Mod ) % Mod );
    }
    return 0;
}